OO_U1 - 数学表达式
Hw1
这本是一个描述本人思路的草稿,后决定还是整理一下,发到公屏交流一下))
要求
读入一个含:
- 加,减
- 乘
- 乘方
- 至多一层括号(建议考虑多层的拓展)
的 单变量(e.g. 字母x) 表达式。
输出:
- 展开所有括号
- 结果尽可能短
构造
我们可以继续沿用先前的逻辑,不过需要针对乘方进行优化(用一个我看得懂,杂揉了RegEx的写法,严谨定义请参阅参考书):
1 | - Expr:(+|-){0,1}term | expr(+|-)term |
为了处理幂函数,我们引入Factor的下一级SubFactor:当前定义下,为^
两端的对象,可为数字,变量或表达式。
此时,我们的指数一定为一个正数,这里SubFactor涵盖指数会不会有问题?在Parser标记的过程,不会;但在后面由标记好的Expr,得到多项式的过程中,就有可能出问题了。
多层括号嵌套
看了OOpre.hw7的都知道,那边的实现之所以不能处理多层嵌套,是因为在最低层次中引入了SubExpr;我们只需把SubExpr换成Expr,就可以处理多层括号嵌套了。
发病
这是一个在参考书的定义下不可能出现的情况,但仍然值得考虑:
1 | +-++---+++-009+b |
对应regex:
1 | (\+|-){0,1}((\d|\+|-)+) |
实际情况中,至多只可能出现三个连续的符号,但考虑一下也好。
继续构造
lexer
将输入tokenize。
分以下几类:
+
-
*
^
(
)
- 数字:调用parseNum(),分析出数字。此时我们先不考虑符号数的问题。
空字符直接跳过,毕竟在我们的定义中,空格不存在语义;不关心其数量而直接跳过,并无影响。
为什么在parse前要tokenize?这对后续拓展其实是有利的,比如说,变量名字不是一个字符x,而是多个字符时。
符号化简
我们认为,此时各个Term的连接应该都是加号。因此,我们需要想一个处理正负的方法。
我们需要对符号进行简化,得到唯一的正负标识reversed
。
这个reversed
标记该放到哪一层呢?
1 | 此时,我们应在最小单元处,进行加减号的化简;因此,我们决定,在parseSubFactor()过程中进行加减号的吞并,同时使用一标识符,指示SubFactor是否取反。 |
仔细思考发现,上述思路对于以下样例处理存在问题:
1 | +-5+-x^5 |
幂函数整体是一个正值。因此,我们处理正负的问题,应该停留在Factor层次。处理连续符号的过程,因此也放在Factor处进行。
为此,我们还需修改Factor类的构成:除SubFactor容器外,还需记录一个boolean reversed
.
具体实现为:
- Expr:parse方法需提供
reversed
,指示默当前正负;直接向下parse,并传递reversed
。 - Term:符号可认为只对第一个乘数有影响,故只将该
reversed
传递到第一个Factor,其余Factor的reversed全设为false;继续向下parse - Factor:先处理符号。 当前读到+保持
reversed
不变,读到-对reversed
取反。完成处理后,使用处理好的reversed
新建Factor对象,再进行下一层的parse(方法同现有的类似,不再赘述)。 - SubFactor:分三类情况,数字,变量和表达式。仿照现有思路处理即可。不过,对于表达式,我们此时调用parseExpr()时,传入的
reserved
应为false,因为我们已经在其上一级Factor处理好了符号。
这样一来,我们逐层向下传递了各个Factor的正负属性,从而为下文进行多项式转换提供便利。
多项式转换
我们通过Parser.parseExpr()
,得到了一个处理(或者说,标记?)后的Expr
。
考察最终化简式,可以得知其形式为:
$$\sum a*x^b$$
因此,我们需要构造:
Mono
类:一个单项式Poly
类:一个多项式,使用容器存储其包含的单项式
同样,我们认为,此时各单项式间连接只有加法。
如何定义Mono?其中包含:
BigInteger multiplier
:aString var
:xBigInteger exp
: b
针对纯数字的表达,我们规定:
- 值全部存储在
multiplier
中 var
此时为空串""
,为变量可能为多字符的情况准备exp
恒为1
在这个思路的指引下,我们引入一个处理器Flattener
,将已进行标记的表达式expr
“拍扁“,得到一个满足上式的多项式。此时,我们并不需要考虑化简的问题;化简的过程,我们在Poly类内实现一个方法即可。
为何要多一个Flattener? 感觉上,边Parse边获取单项式似乎是可行的,但为了高内聚低耦合,还是把获取单项式的过程独立出来吧。
Flatter中需要实现的方法:
getPoly()
:将表达式转为多项式getMono()
:逐层得到单项式,返回一个单项式容器;显然,要根据传入的是Expr/Sub/Factor来进行不同的处理
getPoly()
调用getMono(Expr)
,随后将容器包装为Poly对象。
我们在此仍然采取递归下降的思路,对已标记的Expr进行处理。根据传入对象类别划分:
Expr:创建一单项式容器
monoList
;遍历包含的Term,由getMono()得到子容器;此时是加号,简单合并各容器即可。Term:遍历Factor,得到各子容器;此时是乘号,调用一个多项式乘法方法,得到存有单项式的一个容器
Factor:过程略有复杂。
在当前定义下,必为a^b
的形式。若为x^b
,直接构建新的Mono
,加入将返回的单项式容器;若为<num>^b
,则直接进行计算,按照上文中,纯数字下单项式的约定,构建单项式;若为<expr>^b
,则调用一个多项式求幂方法,得到一系列单项式,最后加入容器。在得到单项式,返回容器之前,还记得Factor的
reserved
属性吗?此时,若其为true,则需要调用一个取反方法,将各个单项式的系数取反。
好的,现在我们还要做:
- 多项式乘法:多次单项式乘法
- 多项式求幂:多次调用多项式乘法即可
- 取反:将各个单项式的系数取反。
- 单项式乘法:功能不赘述。
不过,我们的乘数为0,乘后指数为0的情况都需要在此处理。
这三者的实现其实很简单,这里就不再赘述,不过可以提一下多项式求幂:
在定义中,m^0=1
,我们怎么实现这个逻辑呢?显然,我们求幂返回的是个单项式容器;故,我们在方法被调用的开始,初始化一个只含单项式:数字1的容器;随后,根据次幂,将其同底数多项式相乘指数次即可。
一番操作后,我们就得到了一个未化简的多项式对象Poly了。
多项式化简
思路很简单:遍历单项式容器,合并同次幂单项式。
需要对单项式为数字(即,var.equals("")
)单独开情况处理。不用担心指数为0的情况,上面的单项式乘法里,我们已经处理掉了。
限于篇幅,且实现也不困难,这里就不展开说了。
Hw2
引入了两个新功能:
- 三角函数:
sin
,cos
- 自定义递推函数
其他的定义可以认为没改。我们逐个分析。
递归函数解析
也可以参考这篇帖子,其思路也很不错,本人思路也有不少与之相近之处
这是本次作业里较为头疼的一点,要怎么办呢?
书接上文,我们在解析表达式时,在Factor
下再加了一层SubFactor
。一番分析可知,递归函数调用
正是属于SubFactor
这一层次。那么,我们能不能在parseSubFactor()
中添加调用对应的处理规则,使得我们parse函数调用的时候,得到一个完全展开的表达式呢?
是可以的。在此之前,我们需要搓一个**展开递归函数的“求解器”Solver
**。
求解器
我们这里的整体思路是:
- Parser解析输入表达式时,读到调用,交给Solver处理;
- Solver通过调用序号,得到调用对应的表达式;此时,我们不要求此处得到的表达式完全展开
- 解析这一表达式;遇到调用,则递归重复上述思路。
我们当然先要知道递归函数定义如何。我的处理是:
- 先把各定义Tokenize为Token串;
- 非递归定义的Token串:存入一个以序号为索引的定义表内
- 递归定义的Token串:单独存储。
至于为什么这么做,这就要看我们的求解过程了;我们此时先不管形参转实参的问题:
- 对传入的调用序号,先查定义表内有没有该序号,有则直接解析表项的Token串,没有则继续:
- 定义表不存在该序号,则获取递归定义的Token串,并将其中不定序号
n
对应的Token,换成序号对应的数字Token - 解析这一替换好的Token串副本。随后,就是我们上面的整体思路。
问题来了,我们要怎么解析递归表达式?我们这里的Token串仍然是表达式,复用我们写好的Parser即可,不过需要些许更改:
- 添加SubFactor为调用时的处理方法,并解析出调用的
序号
与参数
(上面已经提到) - 序号的解析应该支持
<num>
和<num>-<num>
的形式,为递归做准备 - 实现形参替换
形参替换
我们能不能在Parser进行处理的时候,就直接自动把变量解析成实参呢?
答案是有的,我们只需要略微修改Parser,以及parseSubFactor()
时,读到变量类型的处理方法:
- Parser:添加属性:符号查找表
HashMap<String,Factor>
parseSubFactor()
:碰到变量先查表,如有对应实参,则返回实参的Factor对象,没有则返回变量- 显然,我们还要把Factor分类到SubFactor里。
在我们解析输入函数时,我们向parse()
传入空表;而在解析递归函数时,我们则先把变量建立好对应的查找表,再在调用的parse()
中传入递归函数的符号查找表。
至此,我们即可展开递归函数并传递变量,完成原设计中标记表达式的功能。
获取多项式
我们这里先不管三角函数。
Flattener
这里本没有什么好说的,但是:参数必须是Factor类型,而我们把Factor类归在了SubFactor类下,故这里也需补充对应获取多项式的逻辑…
事实上,参数完全可以视作
Expr
类,毕竟参数内容是由你的parse方法得到的,而且递归下降的原理也告诉我们,这么处理没问题;视作表达式来处理还更方便,因为不用把Factor归进SubFactor,维持我们Hw1的处理逻辑就行;但题目这么说就这么做吧
这里我们先在“标记”阶段处理掉了递归函数展开,因而获取多项式的部分不需大改,这算是低耦合的好处吧。
单项式结构的修改
由于三角函数的引入,我们不得不修改单项式的定义!
现定义单项式如下:
$$a*\prod
其中:$$unit = <Var|TrigFunc>^n$$Var
代指变量,TrigFunc
代指三角函数。
因此,我们只需要一个BigInteger
存进乘数,一个ArrayList<Unit>
存入后面累乘的幂函数。
在修改了单项式的定义后,是不是需要大规模的重构呢?
先看Flattener
:
- 构造方法:我们在构造方法处使用多态,从而兼容先前构造接口
- 多项式求幂/相乘:只涉及
ArrayList<Mono>
的相关处理,在这一层次不涉及Mono
内部操作,维持现状即可,算是万幸 - 单项式相乘:这个没办法,必须重写;
我的重写思路如下:
- 分两步进行:
- 第一步:简单的乘数相乘,幂函数容器合并
- 第二步:合并底数相同的幂函数
第二步中如何比较底数相等,以及如何合并难度不大,留给读者自行探索。
再看负责多项式化简的Poly
:
- 属性不用更改,本来就是
Mono
容器 - 出问题了!合并同类项的
mergeMono()
要大改!
mergeMono()
分两步:
- 比较多项式是否为同类项,是则合并
- 进行三角函数的化简,这个后面再提
三角函数
这才是本次作业最头大的问题,主要在于化简的复杂度实在太高。
TrigFunc
与TrigFuncFactor
我们引入这两个新的类。
TrigFuncFactor
在Parser内使用,其内存放三角函数的类型,及参数对应的Factor
TrigFunc
在处理成多项式后使用,其内存放三角函数的类型,及参数对应的多项式
三角函数与函数调用被放在了“变量因子”层次,同之前幂函数在一个层次。因此,我们决定,将与TrigFuncFactor
置于SubFactor
层次,这对sin()^2
情况的处理亦有好处。
需要在Flattener和Parser处编写针对三角函数的规则,这里不再赘述。
化简
我选择复现讨论区内已有方法,化简规则看这个基本就够了。不过这篇帖子里讲的是是单次化简。
考虑这样一个输入:
$$(cos(x)^2-sin(x)^2)^2+sin(2x)^2$$
理想的化简结果是1
;显然,单化简一次是不够的!
我们引入这样一个多重化简机制:
- 两个容器:原始单项式集合
monoList
和结果newMonoList
- 外层套
while()
,由一个布尔变量proceed
指示是否继续重复化简 - 引用一个写回缓存区
buffer
,实现“化简之后,把结果加回正在遍历的结果列表”的效果 - 判断单项式集合中
mono
与newMonoList
中元素是否可化简: - 若能,则将合并结果写入缓存,并将此
mono
从原始集合中移除; - 若不能,将此
mono
移动到结果列表中;也就是说,mono
无论如何都得删。 - 双层遍历完成后,**若缓存为空,则说明不可化简,
proceed
设为否;反之,则将缓存内容写回newMonoList
**。
示意如下:
1 | boolean proceed = true; |
Hw3
引入非递归自定函数与求导因子。
SubFactor引入上述两个新元素,对应修改Flattener规则
求导规定成dx(<Expr>)
;在Flattener.getMono(Factor)
中,读到求导因子的Subfactor,则将里面的<Expr>
化成多项式,随后逐单项式,运用求导规则,获得新的表达式。
可以造一个单项式求导器。
非递归自定函数,按照现有实现改进即可。考虑到我们写递归函数求解器的写法,我们甚至可以直接复用。
改Solver
复用已有的Solver。
首先要改lexer,把两个自定函数的符号进行分类,分类就继续分到FUNC
内;
接下来是Parser部分;我们在处理递归函数的时候,写了这么一个东西:
1 | lexer.forward(); // Skip LCurly |
我们在此次修改时,需要这么做:
- 读取当前Token,看是圆括号还是花括号
- 圆括号->普通函数,花括号->递归函数
- 圆括号默认调用次数为0
随后,目光转向Solver;
在我初始化Solver时,我采用了如下写法,以获取n
行的函数定义:
1 | Solver(int n) { |
我们初始化一般函数时,n
设成1;递归函数,n
为3.
其中的classify()
方法,是根据输入的定义式,判断递归表达式的类型,从而决定将定义放入递归定义,还是定义表内;
1 | classify() { |
用同样的思路,在普通函数时,让typeToken变成”0”;随后,就可顺利复用Solver。
那么,我们怎么实现多个函数的解析呢?
- 首先,我们需要给
Solver
添加String name
属性,从而记录当前求解器解的是哪一个函数; - 随后,我们需要构建一个按名称的函数求解器表,将其传给Parser;
- Parser在遇到函数关键字时,查找求解器表,获得求解器,随后求解得到表达式。
这部分就成功解决了,接着看求导。
加求导
首先,我们要在Lexer里面加dx
的规则,这就不多说了。
求导因子会出现嵌套,比如:
1 | dx(dx(x^2)+x^3) |
我们此时仍然不用担心,递归下降的原理保证其可以被处理;我们只需在getMono(Factor)
处正确获取多项式即可。
getMono(Factor)
处,读到求导因子,调用一个求导器,获取实际多项式。
求导器
为方便求导的进行,我们决定对一个多项式求导。也就是说,我们需要先将dx(<expr>)
中的表达式先转换为多项式,再进行我们求导的过程。
我们需要求导的表达式,符合如下一般形式:
$$expr = \sum{a*\prod{
我们将其分为以下层次,分别求导:
- 多项式:如上
- 单项式:$a*\prod{
^b}$ - 幂函数:$
^b$ - 底数:$
$
这样即可应对链式法则中,幂函数之底数为三角函数的问题。
各层规则如下:
- 多项式:对各单项式求导,合并各次求导所得多项式
- 单项式:实现乘法法则,得到求导后多项式
- 幂函数:
先假设<base>
为一个整体,按照幂函数的求导方法正常进行;随后,将结果与底数求导结果相乘,实现链式法则。这里可能需要对^0
,^1
等情况做特殊考虑。 - 底数:返回一个多项式
数字:求导为0;
变量:求导为1;
三角函数:sin,cos按各自方式求导(内部表达式视为整体)后,与内部表达式的求导结果相乘,实现链式法则。
不难注意到,我们上面需要用到多项式乘法;调用我们已实现的方法即可。
拓展三角化简
在Hw2中,我没有搓sin的二倍角化简。在本次作业中,由于出现可化简情况的概率大幅增大,我们决定补齐这一化简策略。
$$(cos(x)^2)’=-2cos(x)sin(x)=-sin(2x)$$
为了防止化简后,输出长度不减反增,我们规定其:
- 在其它三角化简后进行。
- 仅在sin,cos指数均为1时进行
还有化简本身的规则:
- 乘数绝对值大于1(因为我们的系数是
BigInteger
).
总结
回顾本次作业,我发现自己的最终成果存在以下问题:
- Flattener中,
ArrayList<Mono>
与Poly
类混用;这是因为,Poly类是在我发现多项式化简需求后才引入的;我没有狠下心,将单项式容器全部重构为Poly
类,导致Flattener
处画风相当混乱; - 各方法所属的类并未妥善划分;我的多项式/单项式乘法全部放在了
Flattener
中。虽说获取多项式需要这些方法,但仔细想来仍然不合理:多项式有关计算,应该在多项式类中才对; - 部分过程未打包为方法,导致可读性下降:最明显的,就是我赶工赶出来的三角函数化简。
- 不敢
@Override
,导致实现深克隆的过程未被打包为方法,而直接出现在过程中;
日后多加改正。
OO_U1 - 数学表达式